package NC70_单链表的排序;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null){
            return head;
        }

        // 使用快慢指针寻找中点
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;   // 后半部分
        slow.next = null;

        // 递归左右两边进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);

        // 创建新的链表
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        // 合并 left right 两个链表
        while (left != null && right != null){
            if (left.val >= right.val){
                cur.next = right;
                right = right.next;
            }else {
                cur.next = left;
                left = left.next;
            }
            cur = cur.next;
        }
        // 添加未对比的链表部分判断左链表是否为空
        cur.next = left != null ? left : right;
        return dummyNode.next;
    }
}